package com.lw.leetcode.tree.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/11 15:01
 */
public class CountHighestScoreNodes {


    public static void main(String[] args) {
        CountHighestScoreNodes test = new CountHighestScoreNodes();

        // 3
//        int[] arr = {-1, 2, 0, 2, 0};

        // 2
        int[] arr = {-1,2,0};

        int i = test.countHighestScoreNodes(arr);
        System.out.println(i);
    }

    private int n;
    private Node root;
    private long max = -1L;
    private int count = 0;

    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        getTree(parents);
        find(root);
        return count;
    }

    private int find(Node node) {
        if (node == null) {
            return 0;
        }
        int l = find(node.left);
        int r = find(node.right);
        int l1 = l == 0 ? 1 : l;
        int r1 = r == 0 ? 1 : r;
        long p1 = (n - 1 - l - r) == 0 ? 1 : (n - 1 - l - r);
        long p = p1 * l1 * r1;
        if (max == p) {
            count++;
        } else if (p > max) {
            count = 1;
            max = p;
        }
        return l + r + 1;
    }

    private void getTree(int[] parents) {
        Map<Integer, Node> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Node node = map.get(i);
            if (node == null) {
                node = new Node();
                map.put(i, node);
            }
            int v = parents[i];
            if (v == -1) {
                root = node;
                continue;
            }
            Node p = map.get(v);
            if (p == null) {
                p = new Node();
                map.put(v, p);
            }
            if (p.left == null) {
                p.left = node;
            } else {
                p.right = node;
            }
        }
    }

    class Node {
        private Node left;
        private Node right;
    }

}
